package com.gem.day04;

/**
 * 本类用来演示递归算法
 * 
 * 递归算法的本质:在方法体内自己调用自己的过程
 * 注意: 使用递归必须指定递归出口,否则将会堆栈溢出错误
 * 
 * 优点:
 * 可以使用极少的代码完成具有规律性的复杂运算
 * 
 * 缺点:
 * 递归算法极其消耗系统资源,性能极其低下
 * 
 * @author easonsy
 * 2020年7月21日 上午9:13:51
 */
public class RecursionDemo {
	public static void main(String[] args) {
		System.out.println(fac1(10));
		System.out.println(fac2(10));
		System.out.println(feibo(10));

		for (int i = 1; i <= 10; i++) {
			for (int j = 1; j <= i; j++) {
				System.out.print(yanghui(i, j) + "\t");
			}
			System.out.println();
		}
	}

	/**
	 * for循环阶乘
	 */
	public static long fac1(int num) {
		long result = 1;
		for (int i = num; i >= 1; i--) {
			result *= i;
		}
		return result;
	}

	/**
	 * 递归阶乘
	 * 10! = 10*9! ... 1!
	 */
	public static long fac2(int num) {
		//递归出口
		if (num == 1) {
			return 1;
		}
		return num * fac2(num - 1);
	}

	/**
	 * 斐波那契数列
	 * 1 	1	2	3	5	8	13	21	34   55...
	 */
	public static int feibo(int pos) {
		if (pos == 1 || pos == 2) {
			return 1;
		}
		return feibo(pos - 2) + feibo(pos - 1);
	}

	/**
	 * 杨辉三角形
	 * 	1
	 * 	1		1
	 * 	1		2		 1
	 * 1		3		 3			1
	 */
	public static int yanghui(int x, int y) {
		if (x == 1 || y == 1 || x == y) {
			return 1;
		}
		return yanghui(x - 1, y) + yanghui(x - 1, y - 1);
	}
}
